package 栈和队列;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class LC_239滑动窗口最大值 {
    public static void main(String[] args){
        int[] nums={1,3,-1,-3,5,3,6,7};
        int k=3;
        System.out.println(Arrays.toString(maxSlidingWindow(nums,k)));
    }
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if(k==0||nums.length==0) return new int[0];
        //双端队列
        Deque<Integer> deque=new LinkedList<>();
        //结果
        int[] res=new int[nums.length-k+1];
        for(int j=0,i=1-k;j<nums.length;j++,i++){
            //队头元素与窗口第一个元素相等时，移除对头元素
            if(i>0 && deque.peekFirst()==nums[i-1])
                deque.removeFirst();
            //窗口最后一个元素>队尾元素，把所有小于窗口最后一个元素的值全部弹出
            while(!deque.isEmpty() && deque.peekLast()<nums[j])
                deque.removeLast();
            //将窗口元素加入队尾
            deque.addLast(nums[j]);
            //队头为最大值
            if(i>=0)
                res[i]=deque.peekFirst();
        }
        return res;
    }

}
//class MyQueue{
//    Deque<Integer> deque=new LinkedList<>();
//    void poll(int val){
//        if(!deque.isEmpty() && val==deque.peek())
//            deque.poll();
//        deque.add(val);
//    }
//    void add(int val){
//        //getLast()返回Deque的最后一个元素或尾部
//        while(!deque.isEmpty()&&val>deque.getLast())
//            deque.removeLast();
//    }
//    int peek(){
//        return deque.peek();
//    }
//
//
//}
